1. Field of the Invention
The present invention relates generally to convolution for examination using an image device and, more particularly, to a method and apparatus for high speed convolution designed to process high speed convolution irrespective of a mask size through a novel image file structure a linearity of the convolution and overcome problems with the related art convolution processing that cannot be actually realized due to an excessive processing time though examination reliability is enhanced with an increase in the mask size for the convolution.
2. Discussion of Related Art
In an image processing, convolution refers to a procedure of operation to obtain corresponding pixel values by multiplying the values of pixels surrounding image data in an area such as a kernel area by kernel values and summing the resulting values, in a case where the kernel center is matched to each pixel of the image data through an operation of a kernel composed of numerals and the image data.
When the individual pixel value of image data is I(x,y), the mask size (2m+1)xc3x97(2n+1) and the mask value M(x,y), the resulting value of operation for each pixel can be expressed by:       ∑          xe2x80x83        ⁢          (              x        ,        y            )        =            ∑              i        =                  -          m                            i        =        m              ⁢          xe2x80x83        ⁢                  ∑                  j          =                      -            n                                    j          =          n                    ⁢              xe2x80x83            ⁢                        I          ⁢                      (                                          x                +                i                            ,                              y                +                j                                      )                          xc3x97                  M          ⁢                      (                                          i                +                m                +                l                            ,                              j                +                n                +                l                                      )                              
Here, the index of the image data out of a range is zero and that of the mask value M(l.j) is positive.
FIG. 1 shows a one-dimenisional example of the calculation procedure.
A filter is generally used in the examination process through image processing and there are some cases where quality of output images is changed according to the mask size. When the mask size is increased, the image data is insensitive to the noise component and the user has many values to control so that more accurate values can be obtained. However, there is a need of multiplication and summation for the individual pixels as many as the mask size in the operation procedure. Therefore, the operation procedure takes more time with an increase in the mask size. This results in limitation of the mask size in actual applications.
As well known, the convolution procedure is to obtain the resulting value of the individual pixel by multiplying the values corresponding to the pixels and summing the multiplication results. However, this procedure involves a problem in that the number of calculations rapidly increases with an increase in the size of the filter. To solve the problem, there have been suggested many inventions in which the two-dimensional mask is divided into one-dimensional ones, or the calculations are performed in real tine by use of a high speed hardware.
For the related art method using the hardware, U.S. Pat. No 5,119,444 discloses Laplacian and Gaussian simulations using the hardware. Here, a simplest Laplacian filter and three binomial filters are sequentially used to constitute the hardware for 7xc3x977 Gaussi an simulation.
FIG. 2 shows that use is made of a delay to store a target pixel value and its surrounding pixel values during image acquisition according to prior art. Here, the reference numeral 42 represents an SEM for image acquisition, the reference numeral 43 an analog/digital converter for converting an analog video signal to its corresponding digital image data, the reference numeral 44 a pattern compensator for outputting pattern compensation data. The reference numerals 51 and 52 indicate switches, the reference numeral 50 a delay, and the reference numerals 45 and 49 output lines for storing, in a latch, image data obtained by combining signals via the switches 51 and 52 and signals via a plurality of delays.
FIG. 3 is a diagram illustrating a procedure of obtaining Laplacian in a manner of hardware, in which the Laplacian is obtained by summing image values of pixels surrounding a target pixel out of five image values acquired in FIG. 2 via summation circuits 60, 61 and 64, multiplying at a shifter the image value of the target pixel except for the four images values summed at the summation circuits 60 and 61, and subtracting at a subtractor 68 one of the two values obtained from the shifter 60 from the other value.
FIG. 4 is a diagram illustrating a procedure of obtaining Gaussian in a manner of hardware, in which the one-dimensional Gaussian is obtained by delaying the digital video sign cals obtained in FIG. 3 via delays 78 and 79 and then using summation circuits 70 and 74 and shifters 72 and 77.
FIG. 5 is a diagram illustrating a procedure of obtaining 7nxc3x977n Gaussian using the circuit shown in FIG. 4 in a manner of hardware.
However these related art convolution apparatuses has a disadvantage in that their speed depends on the structure of a hardware and is not easy to change and that a variety of filters are difficult to realize.
Further, in a case where it is needed to increase the filter mask size in order to enhance the quality of results in a real-time calculation, the speed of the hardware is deteriorated or the cost is greatly increased.
It is therefore an object of the present invention to provide a method and apparatus for high speed convolution, designed to process high speed convolution irrespective of a mask size through a novel image file structure and linearity of the convolution and overcome problems with the related art convolution processing method and apparatus that cannot be actually realized due to an excessive processing time though examination reliability is enhanced with an increase in the mask size for the convolution.
To achieve the first object of the present invention, there is provided a method for high speed convolution including the steps of: determining a convolution mask by dividing a theoretical mask into a predetermined number of areas as many as a multiple of sampling intervals of target data; generating accumulative image data of a target image to be convolved and storing them in a memory; calculating image summation data in an area corresponding to the area of each step of the mask from the accumulative image data; and calculating the convolution of pixels from the corresponding area image data and mask step values corresponding to the area.
The present invention also provides an apparatus for high speed convolution including an accumulative image data generator for converting an input image of a camera to digital image data, adding the converted image data to image summation data from an origin on the present horizontal line to a previous pixel, and adding the result value to a pixel value in a rectangular area formed by an origin and pixels on the line previous to a present pixel, to generate an accumulative image data; a corresponding area data calculator for extracting a predetermined number of partial area data from the accumulative image data generated from the accumulative image data generator, selectively adding and subtracting the extracted partial area data to obtain image summation data of the corresponding area, and outputting a mask step value corresponding to the area; and a pixel convolution value output for multiplying the corresponding area image data obtained from the corresponding area data calculator by the corresponding mask step value and summing the multiplication results to output a pixel convolution value.